#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int dijkstra() {
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;
	
	for (int i = 0; i < n - 1; ++ i) {
		int t = -1; // 先将目标点给初始化为-1
		for (int j = 1; j <= n; ++ j) // 遍历所有点
			if (!st[j] && (t == -1 || dist[t] > dist[j])) // 如果该点没用被确定过且刚开始找目标点或者有距离集合更近的点
				t = j; // 就将目标点更新为该点
		
		st[t] = true; // 确定该点后将它标记为已被确定过的状态
		
		for (int j = 1; j <= n; ++ j) // 以找到的目标点更新它的所有联通点的距离
			dist[j] = min(dist[j], dist[t] + g[t][j]);
	}
	
	if (dist[n] == 0x3f3f3f3f) return -1; // 如果dist[n] == 0x3f3f3f3f,则说明无法从1点走到n点，就返回-1
	return dist[n]; // 如果能从1点走到n点，就返回该点到1点的距离（即dist[n]）
}

int main() {
	cin >> n >> m;
	
	memset(g, 0x3f, sizeof g); // 将所有边权初始化为负无穷
	
	for (int i = 0; i < m; ++ i) { // 读入边
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		g[a][b] = min(g[a][b], c); // 处理重边，将边权更新为最短的
	}
	
	int ans = dijkstra(); // 得到最短路的距离
	cout << ans << endl; // 输出答案
	
	return 0; // 结束快乐~
}